Algoritmi Genetici (AG)sono euristiche di ricerca globale stocastiche ispirate ai principi dell'evoluzione naturale, in particolare alla "sopravvivenza del più adatto" darwiniana e al ricombinazione genetica.
1. Framework di Rappresentazione
- AG Canonici:Utilizzano rappresentazioni binarie o in codice Gray per codificare le variabili decisionali.
- AG a Codifica Reale (RCGA):Manipolano direttamente vettori in virgola mobile, spesso più efficienti per l'ottimizzazione continua.
2. Il Ciclo Evolutivo
Un processo iterativo di valutazione, selezione e riproduzione. Un concetto fondamentale è la distinzione tra il Genotipo (la stringa binaria codificata/cromosoma) e il Fenotipo (il valore della variabile decisionale decodificato nello spazio del problema reale).
La mappatura da una stringa binaria a un valore reale $x \in [a, b]$ è data da:
$$x = a + \frac{valore\_decimale \times (b - a)}{2^L - 1}$$
Dove $L$ è la lunghezza in bit del cromosoma.
Ripidezze di Hamming
Fai attenzione alle Ripidezze di Hamming nella codifica binaria standard — situazioni in cui numeri decimali adiacenti (come 7 e 8) hanno pattern binari radicalmente diversi (
0111 vs 1000), rendendo difficile per l'AG eseguire ricerche localizzate.
Implementazione in Python: Decodifica Binario-a-Reale
Domanda 1
Perché il codice Gray è spesso preferito rispetto alla codifica binaria standard negli AG?
Domanda 2
Se la probabilità di mutazione (p) è impostata troppo alta (es. p = 0.5), qual è il risultato probabile?
Studio di Caso: Ottimizzazione di un Componente per Ponte
Leggi lo scenario qui sotto e rispondi alle domande.
Stai ottimizzando il design di un componente per ponte dove la variabile decisionale è "Spessore del Materiale".
- Lo spessore deve essere compreso tra 0,0 mm e 10,23 mm.
- Stai utilizzando un AG canonico con una rappresentazione a 10 bitstringa binaria.
Q
1. Se un individuo ha il cromosoma
0000000000, qual è lo spessore decodificato?Risposta: 0,0 mm
La stringa binaria
La stringa binaria
0000000000
corrisponde a 0 in decimale. Usando la formula $x = a + \frac{decimale \times (b-a)}{2^L - 1}$, otteniamo $0,0 + \frac{0 \times (10,23 - 0,0)}{1023} = 0,0$.
Q
2. Calcola la precisione della ricerca (il cambiamento minimo possibile nello spessore) per questa configurazione a 10 bit.
Risposta: 0,01 mm
La precisione è definita dal range diviso per il valore decimale massimo possibile. $\frac{10,23 - 0}{2^{10} - 1} = \frac{10,23}{1023} = 0,01\text{mm}$.
La precisione è definita dal range diviso per il valore decimale massimo possibile. $\frac{10,23 - 0}{2^{10} - 1} = \frac{10,23}{1023} = 0,01\text{mm}$.
Q
3. Durante la selezione, l'Individuo A ha un adattamento di 10 e l'Individuo B ha un adattamento di 30. Usando la selezione con la Ruota della Roulette, qual è la probabilità che B sia scelto rispetto ad A?
Risposta: 75%
Adattamento totale = $10 + 30 = 40$. Probabilità di selezionare B = $\frac{30}{40} = 0,75$ o 75%. (Un rapporto 3:1).
Adattamento totale = $10 + 30 = 40$. Probabilità di selezionare B = $\frac{30}{40} = 0,75$ o 75%. (Un rapporto 3:1).